package ds.stack.app;

import ds.stack.StackX;

/**
 * 功能：从以字符串表示的运算表达式求结果
 */
public class FormularParse{
	InToPost ip;
	ParsePost pp;
	String input;
	
	public FormularParse(String input)
	{
		this.input = input;
	}
	
	public long doParse() throws Exception
	{
		ip = new InToPost(input);
		pp = new ParsePost(ip.doTrans());
		return pp.doParse();
	}
	
	public static void main(String[] args) throws Exception
	{
		System.out.println(new FormularParse("5+4/(2+2)*5+1-9").doParse());
	}
}

/**
 * 功能：中缀表达式转后缀表达式
 */
class InToPost {

	private String input;
	private String output="";
	private StackX theStack;
	//-----------------------------------------------------
	public InToPost(String input) { // constructor
		this.input = input;
		theStack = new StackX(input.length());
	}
	
	public String doTrans() throws Exception
	{
		for(int i=0;i<input.length();i++)
		{
			char ch = input.charAt(i);
			switch (ch) {
			case '+':
			case '-':
			case '*':
			case '/':
				gotOper(ch);
				break;
			case '(':
			case ')':
				gotBracket(ch);
				break;
			default:
				output = output + (char)ch;
				break;
			}
		}
		while(!theStack.isEmpty())
		{
			output = output + (char)theStack.pop();
		}
		return output;
	}
	
	private void gotOper(char ch) throws Exception
	{
		loop:while(!theStack.isEmpty())
		{
			char pCh = (char)theStack.pop();
			switch(pCh)
			{
			case '+':
			case '-':
			case '*':
			case '/':
				if(comparePriority(pCh,ch)<0)
				{
					theStack.push(pCh);
					break loop;
				}
				else
				{
					output = output + (char)pCh;
					break;
				}
			case '(':
				theStack.push(pCh);
				break loop;
			}
		}
		theStack.push(ch);
	}
	
	private void gotBracket(char ch) throws Exception
	{
		if(ch == '(')
		{
			theStack.push(ch);
		}
		else
		{
			while((char)theStack.peek()!='(')
			{
				output = output + (char)theStack.pop();
			}
			theStack.pop();
		}
	}
	
	private int comparePriority(char ch1, char ch2)
	{
		if(ch1 == '+' || ch1 == '-')
			return ch2 == '+' || ch2 == '-'? 0 : -1 ;
		else
			return ch2 == '+' || ch2 == '-'? 1 : 0 ;
	}
	
	public static void main(String args[]) throws Exception
	{
		System.out.println(new InToPost("A*(B+C)-D/(E+F)").doTrans());
	}
}

/**
 * 功能：解析后缀表达式并运算
 */
class ParsePost {

	private StackX theStack;
	private String input;
	
	public ParsePost(String input)
	{
		this.input = input;
		theStack = new StackX(input.length());
	}
	
	public long doParse() throws Exception
	{
		theStack = new StackX(input.length());
		for(int i=0;i<input.length();i++)
		{
			char ch = input.charAt(i);
			switch(ch)
			{
			case '+':
			case '-':
			case '*':
			case '/':
				gotOper(ch);
				break;
			default:
				theStack.push(ch-'0');
			}
		}
		return theStack.pop();
	}
	
	private void gotOper(char ch) throws Exception
	{
		long num2 = theStack.pop(); // 注意顺序
		long num1 = theStack.pop();
		switch(ch)
		{
		case '+':
			theStack.push(num1+num2);
			break;
		case '-':
			theStack.push(num1-num2);
			break;
		case '*':
			theStack.push(num1*num2);
			break;
		case '/':
			theStack.push(num1/num2);
			break;
		}
	}
}